// 1403. 非递增顺序的最小子序列
// 思路：对数组先排降序，如此前 n 项相加大于后 size - n 项相加，
// 此时前 n 项便就是最小子序列，同时也是最大的和


#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

class Solution
{
public:
    vector<int> minSubsequence(vector<int>& nums)
    {
        // 1. 先排序
        sort(nums.begin(), nums.end(), greater<int>());
        // 2. 统计数组和
        int sum = 0;
        for(auto& e : nums) sum += e;
        // 3. 统计元素
        vector<int> ret;
        for(int i = 0, tmpSum = 0; i < nums.size(); i++)
        {
            // 进窗口
            tmpSum += nums[i];
            ret.push_back(nums[i]);
            // 判断
            if(sum - tmpSum < tmpSum) break;
        }
        return ret;
    }
};